/* exercice 2 */


tousdiff([]).
tousdiff([X|Y]):-not(membre(X,Y)).

membre(X,[X|_]).
membre(X,[_|L]):-membre(X,L).

/* ces deux prédicats permettent de tester qu'une liste 
ne contient pas de doublons */

cycle_aux(X,[Y]):-arc(Y,X).
cycle_aux(X,[Y,Z|L]):-arc(Y,Z),cycle_aux(X,[Z|L]).

/* ce prédicat vérifie que sont deuxiéme argument soit 
un chemin dans le graphe, qui termine sur un sommet relié au
premier argument*/

est_cycle([]). 
est_cycle([X|L]):-tousdiff([X|L]),cycle_aux(X,[X|L]).

est_cycle_hamiltonien(L):-est_cycle(L),nombre_sommets(N),length(L,N).

trouve_cycle_hamiltonien:- perm([a,b,c,d,e,f],L),
est_cycle_hamiltonien(L).


/* exercice 3 */

    /* une solution possible:  génerer la liste des diviseurs propres de n,
    puis sommer les éléments de cette liste et vérifier que le résultat est n;
autre solution, plus courte, 
illustrée ici: écrire directement un prédicat à trois places
qui calcule la somme des diviseurs propres de son 2eme argument, en faisant
une récurrence sur son 1er argument*/

aux(0,_,0):-!.
aux(D,N,S):-P is D-1, aux(P,N,R), ((N mod D)=:=0 -> S is R+D; S is R).

est_parfait(N):-P is N-1, aux(P,N,N).


/*exercice 4 */

/* choix raisonnable pour les configuratins: une liste de 2 entiers */

entre(P,Q,P):-P<Q.
entre(P,Q,R):- S is P+1, S<Q, entre(S,Q,R).

move([X,Y],[Z,Y]):-entre(0,X,Z).
move([X,Y],[X,Z]):-entre(0,Y,Z).
move([X,Y],[Z,T]):-min(X,Y,M),S is M+1,entre(1,S,Q),Z is X-Q,T is Y-Q.

    min(X,Y,Z):-(X<Y->Z is X; Z is Y).

gagne([0,0]).
gagne(P):-move(P,Q),not(gagne(Q)).